package com.datastructures2.unionFind;

import edu.princeton.cs.algs4.In;

/**
 * @author MaoLin Wang
 * @date 2020/2/2910:44
 */
public class QuickFindUF {
    private int[] id;
    /**
     * 分量数量
     */
    private int count;

    public QuickFindUF(int count) {
        this.count = count;
        this.id=new int[count];
        for (int i = 0; i < count; i++) {
            id[i]=i;
        }
    }

    /**
     * p和q是否在同一个分量
     * @param p
     * @param q
     * @return
     */
    public boolean connected(int p,int q){
        return quickFind(p)==quickFind(q);
    }

    /**
     * 速度快，但无法解决大型问题，因为每次都需要遍历整个id[]数组
     * @param i
     * @return
     */
    private int quickFind(int i) {
        return id[i];
    }
    public int count(){
        return count;
    }


    public void union(int p,int q){
        if (!connected(p,q)){
            for (int i = 0; i < id.length; i++) {
                if (id[i]==id[p]){
                    id[i]=id[q];
                    count--;
                }
            }
        }
    }

}
